//给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 
//
// 
// 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。 
//
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
//输出：4
//解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
//其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 
//n 的值 3 。
// 
//
// 示例 2： 
//
// 
//输入：strs = ["10", "0", "1"], m = 1, n = 1
//输出：2
//解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= strs.length <= 600 
// 1 <= strs[i].length <= 100 
// strs[i] 仅由 '0' 和 '1' 组成 
// 1 <= m, n <= 100 
// 
// Related Topics 数组 字符串 动态规划 
// 👍 598 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class OnesAndZeroes {
    public static void main(String[] args) {
        String[] strs = {"10","1","0"};
        new OnesAndZeroes().new Solution().findMaxForm(strs, 1, 1);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 使用dfs暴力搜也不是不行，就是时间上会比较长
         * 使用dp的话 dp[i][j] 存储的是能取到前i个子串长度最大值？
         * 将m和n作为最大容量，需要再扩充一个维度
         * dp[i][j][k]是存储前i个字符串包含j个0和k个1的子集长度
         * 头一次见三维的dp
         * 状态转移方程比较常规
         * 当前字符串不取：dp[i-1][j][k]
         * 当前字符串取：max(dp[i-1][j][k],dp[i][j-zero][k-one]+1)
         */
        public int findMaxForm1(String[] strs, int m, int n) {
            int len = strs.length;
            int[][][] dp = new int[len+1][m+1][n+1];
            for (int i = 1; i <= len ; i++) {
                int zero = countZero(strs[i-1]);
                int one = strs[i-1].length()-zero;
                for (int j = 0; j <= m ; j++) {
                    for (int k = 0; k <=n ; k++) {
                        dp[i][j][k] = dp[i-1][j][k];
                        if (zero <=j && one <= k){
                            dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-zero][k-one]+1);
                        }
                    }
                }
            }
            return dp[len][m][n];
        }

        /**
         * 可以压缩数组到二维的
         * 压缩空间，从后往前遍历
         */
        public int findMaxForm(String[] strs, int m, int n) {
            int[][] dp = new int[m+1][n+1];
            for (int i = 1; i <= strs.length ; i++) {
                int zero = countZero(strs[i-1]);
                int one = strs[i-1].length()-zero;
                for (int j = m; j >= zero ; j--) {
                    for (int k = n; k >= one ; k--) {
                        dp[j][k] = Math.max(dp[j][k],dp[j-zero][k-one]+1);
                    }
                }
            }
            return dp[m][n];
        }
        public int countZero(String s){
            int res = 0;
            char[] chars = s.toCharArray();
            for (char c : chars){
                if (c == '0') {
                    res++;
                }
            }
            return res;
        }

        /*//dfs暴力搜索
        int res;
        List<String> temp;
        public int findMaxForm(String[] strs, int m, int n) {
            res = 0;
            temp = new ArrayList<>();
            dfs(0,strs,m,n);
            return res;
        }

        private void dfs(int index, String[] strs, int m, int n) {
            if (temp.size()!=0){
                res = Math.max(res, temp.size());
            }else {
                for (int i = index; i < strs.length ; i++) {
                    String s = strs[i];
                    if (s.length()>m+n) continue;
                    int zero = 0;
                    for (char c : s.toCharArray()){
                        if (c=='0') zero++;
                    }
                    int one = s.length()-zero;
                    if (zero<=m&&one<=n){
                        temp.add(s);
                        dfs(index+1, strs, m-zero, n-one);
                        temp.remove(temp.size()-1);
                    }
                }
            }
        }*/
    }
//leetcode submit region end(Prohibit modification and deletion)

}